package com.fw.leetcode.doublepointer;

import com.fw.leetcode.LeetCode;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.PriorityQueue;

/**
 * 295. Find Median from Data Stream
 *
 * The median is the middle value in an ordered integer list. If the size of the list is even,
 * there is no middle value, and the median is the mean of the two middle values.
 *  · For example, for arr = [2,3,4], the median is 3.
 *  · For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
 * Implement the MedianFinder class:
 *  · MedianFinder() initializes the MedianFinder object.
 *  · void addNum(int num) adds the integer num from the data stream to the data structure.
 *  · double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.
 *
 * Example 1:
 *  Input
 *   ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 *   [[], [1], [2], [], [3], []]
 *  Output
 *   [null, null, null, 1.5, null, 2.0]
 *  Explanation
 *   MedianFinder medianFinder = new MedianFinder();
 *   medianFinder.addNum(1);    // arr = [1]
 *   medianFinder.addNum(2);    // arr = [1, 2]
 *   medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
 *   medianFinder.addNum(3);    // arr[1, 2, 3]
 *   medianFinder.findMedian(); // return 2.0
 *
 * Constraints:
 *  -10^5 <= num <= 10^5
 *  There will be at least one element in the data structure before calling findMedian.
 *  At most 5 * 10^4 calls will be made to addNum and findMedian.
 *
 * Follow up:
 *  If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
 *  If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
 */
public class Num_0295 implements LeetCode {

    private interface Solution {

        interface MedianFinder {

            void addNum(int num);

            double findMedian();
        }

        MedianFinder createMedianFinder();

        default void assertEquals(Integer[] stream, Double[] expected) {
            MedianFinder obj = null;
            for (int i = 0; i < stream.length; i++) {
                if (stream[i] == null) {
                    if (obj == null) {
                        obj = createMedianFinder();
                    } else {
                        double result = BigDecimal.valueOf(obj.findMedian())
                                .setScale(1, RoundingMode.HALF_UP)
                                .doubleValue();
                        if (result != expected[i]) {
                            obj.findMedian();
                        }
                    }
                } else {
                    obj.addNum(stream[i]);
                }
            }
        }
    }

    private static class MyHeapSolution implements Solution {

        static class MyMedianFinder implements MedianFinder { // 优先队列(堆)：时O(log n) 空O(n)

            private PriorityQueue<Integer> leftMax = new PriorityQueue<>((a,b)->b-a); // 记录小于中位数的左半部分，求最大值（即中位数）
            private PriorityQueue<Integer> rightMin = new PriorityQueue<>((a,b)->a-b); // 记录大于中位数的右半部分，求最小值（即中位数）

            public MyMedianFinder() {
            }

            @Override
            public void addNum(int num) {
                /*
                 * 数据流中的中位数（难）
                 *     3,4 | 5,6
                 * -> 1        此时不用平衡
                 *     3,4 | 5
                 * -> 1        此时需要从左边移动到右边一个最大的
                 *     4 | 5
                 * -> 7        此时需要从右边移动到左边一个最小的
                 */
                if (leftMax.isEmpty() || num < leftMax.peek()) {
                    leftMax.add(num);
                    if (leftMax.size() > rightMin.size() + 1) {
                        rightMin.add(leftMax.poll());
                    }
                } else {
                    rightMin.add(num);
                    if (rightMin.size() > leftMax.size()) {
                        leftMax.add(rightMin.poll());
                    }
                }
            }

            @Override
            public double findMedian() {
                if (leftMax.size() == rightMin.size()) {
                    return (leftMax.peek() + rightMin.peek()) / 2.0;
                } else {
                    return leftMax.peek();
                }
            }
        }

        @Override
        public MedianFinder createMedianFinder() {
            return new MyMedianFinder();
        }
    }

    private static class MySolution implements Solution {

        static class MyMedianFinder implements MedianFinder { // 升序数据流才能用，不符合题意

            static class Node {
                public int val;
                Node next;
                public Node(int val) { this.val = val; }
            }
            private final Node head = new Node(-1);
            private Node tail = head;
            private int size;

            public MyMedianFinder() {
            }

            @Override
            public void addNum(int num) {
                /*
                 * [1]
                 * [1], [2]
                 * 1, [2], 3
                 * 1, [2], [3], 4
                 * 1, 2, [3], 4, 5
                 */
                Node node = new Node(num);
                size++;
                if (head.next == null) {
                    head.next = node;
                    tail = node;
                    return;
                } else {
                    tail.next = node;
                    tail = node;
                }
                if ((size & 0x1) == 1) {
                    head.next = head.next.next;
                }
            }

            @Override
            public double findMedian() {
                if ((size & 0x1) == 1) {
                    return head.next.val;
                } else {
                    return (head.next.val + head.next.next.val) / 2.0;
                }
            }
        }

        @Override
        public MedianFinder createMedianFinder() {
            return new MyMedianFinder();
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyHeapSolution();
        /* 未过测试用例
         * ["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum",
         *  "findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian",
         *  "addNum","findMedian","addNum","findMedian","addNum","findMedian"]
         * [[],[6],[],[10],[],[2],[],[6],[],[5],[],[0],[],[6],[],[3],[],[1],[],[0],[],[0],[]]
         * => [null,null,6.0,null,8.0,null,6.0,null,6.0,null,6.0,null,5.5,null,6.0,null,5.5,null,5.0,null,4.0,null,3.0]
         * 我的输出：
         * => [null,null,6.00000,null,8.00000,null,10.00000,null,6.00000,null,2.00000,null,4.00000,null,6.00000,null,5.50000,null,5.00000,null,2.50000,null,0.00000]...
         */
        solution.assertEquals(new Integer[]{
                null,6,null,10,null,2,null,6,null,5,null,0,null,6,null,3,null,1,null,0,null,0,null
        }, new Double[]{
                null,null,6.0,null,8.0,null,6.0,null,6.0,null,6.0,null,5.5,null,6.0,null,5.5,null,5.0,null,4.0,null,3.0
        });
        solution.assertEquals(new Integer[]{null,1,2,null,3,null}, new Double[]{null,null,null,1.5,null,2.0});
    }
}
